基數計數有點拗口，但要做的事其實很單純，就是確認一個集合中的元素有多少個，但要去重(dedup)。

舉例來說，[1, 1, 2, 3]這樣一個陣列的基數計數為3。

使用Redis有很多種方法可以做基數計數，因此，要選擇哪個方法取決於要解決的使用案例。這篇文章會解釋在做選擇時有哪些考慮因素。

使用情境

為了更容易理解，我們依然用一個實際例子來說明思考過程。

假設我們需要一個感測器網路(sensor network)的失敗率以便了解感知品質。

因此，我們必須將所有回報的請求記錄下來，並以小時計。若是一個小時內有任何成功回報，就當作感測器還正常工作，反之視為感測器異常。若是感測器異常比例過高，那麼整個感測器網路的報告就視為失敗。

這是感測器網路很常見的使用情境，關鍵在於，我們不希望每次感測器請求進來時都必須先取得小時內的數據來判斷是否已經存在了，例如下面的處理流程。

這樣的流程不僅需要寫入同時也要讀取，如果還記得之前一直提到的讀寫分離，就會知道寫入歸寫入、讀取歸讀取是最好的。

因此，我們應該每一次都把紀錄寫入，讓儲存引擎自動幫我們去重，當然也可以先將資料做點預處理以便讓儲存引擎效率更好。

假設我們有一個感測器A，這個感測器在1/2 1:11、1/3 2:22和1/8的3:00各發出一個請求。

好，接下來讓我們來看看該怎麼使用Redis做基數計數。

Set

我相信我們最直覺的想法就是使用集合Set。在將紀錄加入集合之前，我們先做點預處理，因為根據我們的需求，我們不需要保留分和秒。

//2021y, 0M, 2d, 1h, 0m
const date1 = new Date(2021, 0, 2, 1, 0);
const d1 = date1.toISOString(); 

接著，有了時間之後我們就可以將d1透過SADD加入集合。

SADD sensorA "2021-01-02T01:00:00.000Z"
SADD sensorA "2021-01-03T02:00:00.000Z"
SADD sensorA "2021-01-08T03:00:00.000Z"

為了取得基數計數，我們可以使用SCARD來取得結果。

SCARD sensorA
> 3

用Set實作是最單純的，因為Set會自動去重。

儘管如此，我們無法取得特定時間範圍的結果。舉例來說，如果想要取得2021一月1號到5號的基數計數，Set是辦不到的。

Sorted Set

因此，如果我們想要滿足取得特定時間範圍這個需求，我們可以使用Sorted Set。整個實作和Set其實很類似。

首先，預處理資料。

const date1 = new Date(2021, 0, 2, 1, 0);
const d1 = date1.getTime();

這裡我們不使用ISO格式的時間字串，我們採用時間戳記，以便讓取得特定時間範圍更加容易。接著，我們可以將資料透過ZADD加入了。

ZADD sensorA 1609520400000 1609520400000
ZADD sensorA 1609610400000 1609610400000
ZADD sensorA 1610046000000 1610046000000

要取得基數計數則是ZCARD。

ZCARD sensorA
> 3

另一方面，為了取得特定時間範圍，我們可以透過ZCOUNT給定起始和結束時間。

ZCOUNT sensorA 1609520400000 1610040000000
> 2

Bitmap

我們已經介紹過兩個方案了，但是無論Set或是Sorted Set都無法有效使用記憶體，他們的空間使用都是O(n)。此外，為了維持集合的資料結構，每一筆資料都有一個額外的空間開銷。

當感測器的數量很龐大且要紀錄的時間很長久，那麼Redis使用的記憶體會成長得非常迅速。

那要如何減少記憶體開銷？我們可以用一個特殊的字串延伸結構，Bitmap。Bitmap在空間運用上非常有效率，每一筆資料如同他的名字就是1位元。

但是，資料預處理會比集合類型的處理更加複雜，我們需要取得每一筆時間的偏移量。舉例來說，假設這個感測器網路是在2021/1/1 0:00上線，那麼我們收到請求後就需要計算當下時間和上線時間的偏移量。

const base = new Date(2021, 0, 1, 0, 0);
const date1 = new Date(2021, 0, 2, 1, 11);
const diffTime = Math.abs(date1 - base);
const diffHours = Math.ceil(diffTime / (1000 * 60 * 60));

有了偏移量，我們就將對應的位元設為1。

SETBIT sensorA 26 1
SETBIT sensorA 51 1
SETBIT sensorA 171 1

因此我們就可以透過BITCOUNT取得基數計數。

BITCOUNT sensorA
> 3

BITCOUNT也可以做到某個範圍的計數，因此我們可以給定特定時間區間的起始和結束，正如同我們在Sorted Set做的。

但值得一提的是，BITCOUNT的起始和結束是位元組而不是位元，所以我們必須將起始和結束時間的小時以及「位元組」偏移量計算出來。這個計算有點複雜，為了避免這篇文章失焦，我不會在這示範。

HyperLogLog

最後一個方案是HyperLogLog。這是一種大數據的統計演算法，Redis內建有提供。

無論是Set、Sorted Set或Bitmap記憶體用量都會隨著資料量成長，且都是O(n)，但Bitmap的用量會比前兩者小不少。但即便如此，如果我們要保存十年的資料，對於每個感測器來說，都會佔用85.5KB的空間。

365 * 10 * 24 / 1024 ~ 85.5 (KB)

但如果使用HyperLogLog，那麼記憶體用量就是O(1)，也就是說，無論資料量多大都不會增加記憶體用量。每一個感測器就是固定使用12KB。

整個預處理的過程類似Set。

const date1 = new Date(2021, 0, 2, 1, 0);
const d1 = date1.toISOString();

接著，我們就可以透過PFADD將資料加入HyperLogLog。

PFADD sensorA "2021-01-02T01:00:00.000Z"
PFADD sensorA "2021-01-03T02:00:00.000Z"
PFADD sensorA "2021-01-08T03:00:00.000Z"

要取得基數計數也很容易。

PFOCUNT sensorA
> 3

HyperLogLog沒有完全精準，在資料量很大時會有誤差，誤差率有論文可以參考，這邊就不附了，但這個誤差率對於我們來說其實沒什麼影響，而且HyperLogLog的效能非常好。

結論

讓我們總結一下這四個方案。

這篇文章用的範例很單純，但是，我相信你們都能夠了解每個方案的概念。重要的是，每個方案都有其優點和缺點，正確運用這些方法是工程師們的責任。